import util.TreeNode;

/**
 * Created by loso on 2017/3/9.
 */
public class _108_ConvertSortedArrayToBinarySearchTree {
    public static void main(String[] args) {
        int[] a = {1,3};
        sortedArrayToBST(a);
    }

    public static TreeNode sortedArrayToBST(int[] nums) {
        if (nums.length == 0){
            return null;
        }
        return insertNode(nums,0,nums.length-1);
    }

    public static TreeNode insertNode (int[] nums, int start, int end){
        if(start == end)
            return new TreeNode(nums[start]);
        int mid = (start + end)/2;
        TreeNode treeNode = new TreeNode(nums[(start + end)/2]);
        if(mid>start)
            treeNode.left = insertNode(nums,start,mid - 1);
        if (mid<end)
            treeNode.right = insertNode(nums,mid + 1 , end);
        return treeNode;
    }
}
